package tencent_practice;

import java.util.HashMap;
import java.util.Map;

/**
 * 实现一个LRU缓存，第一次做，旨在练习
 * LRU：当不得不淘汰某些数据的时候（通常是容量已经满了），选择最久未被使用的数据进行淘汰
 */
public class Tencent_146_LRUCache {
    /**
     * 自己先实现一个Node节点，作为后面需要的实际插入的准备
     */
    class Node{
        int k, v;
        Node left, right;
        public Node (int _k, int _v) {
            k = _k;
            v = _v;
        }
    }

    int n;
    // 头尾哨兵节点
    Node head, tail;
    // 这个map用来方便后面的get数据和put数据的时候的操作
    // key 是这个Node节点的val值
    Map<Integer, Node> map;
    public Tencent_146_LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        // 形成双向链表
        head.right = tail;
        tail.left = head;
    }

    /**
     * get()方法就是指，这个页面被使用了
     * 被使用之后就是最新被使用的页面，要放在最上面
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        // 如果已经存在
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            // 如果没有存在，首先要判断map是不是满了
            if (map.size() == n) {
                Node del = tail.left;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }

    // 每次发生了插入的时候，都要进行的一个操作，这个操作的目的就是把新插入的输入放在表头
    private void refresh(Node node) {
        // 先执行一次删除双向链表中存在的node节点
        delete(node);
        node.right = head.right;
        node.left = head;
        head.right.left = node;
        head.right = node;
    }

    // 每次如果发生了数据插入的情况，都要执行一次这个方法
    // 保证每一次表尾的数据都是最久未使用的
    private void delete(Node node) {
        // 首先要保证删除的不是哨兵节点
        // 下面的这个判断，能保证删除的节点是在双向链表里面的
        if (node.right != null) {
            Node left = node.left;
            left.right = node.right;
            node.right.left = left;
        }
    }

}
